1. Field of the Invention
This invention relates generally to the field of digital interface design and, more particularly, to digital storage interface design.
2. Description of the Related Art
In recent years the electronics marketplace has seen a proliferation of appliances and personal electronics devices that use solid-state memory. For example, traditional film cameras have been losing market share to digital cameras capable of recording images that may be directly downloaded to and stored on personal computers (PCs). The pictures recorded by digital cameras can easily be converted to common graphics file formats such as JPEG, GIF or BMP, and sent as e-mail attachments or posted on web pages and online photo albums. Many digital cameras are also capable of capturing short video clips in standard digital video formats, for example MPEG-2, which may also be directly downloaded and stored on PCs or notebook computers. Other devices that typically use solid-state memory include personal digital assistants (PDAs), pocket PCs, video game consoles and MP3 players.
The most widely used solid-state memory devices comprise flash-memory chips configured on a small removable card, and are commonly referred to as flash-memory cards. The majority of flash-memory cards currently on the market typically comprise one of four different types: Compact Flash, Multi Media Card (MMC) and the related Secure Digital Card (SD), SmartMedia, and Memory Stick. Most digital cameras, for example, use Compact Flash cards to record images. Many PDA models use Memory Stick cards to hold data. Some MP3 players store music files on Smart Media cards. Generally, data saved by PDAs and other handheld devices using flash-memory cards are also transferred or downloaded to a PC. In the present application, the term “flash-memory” is intended to have the full breadth of its ordinary meaning, which generally encompasses various types of non-volatile solid-state memory devices.
Generally, data in flash-memory devices may be erased in units of blocks and written in units of pages. Blocks typically designate a minimum Erasable Unit (EU), and consist of a plurality of pages, which serve as a minimum Read/Write Unit (RWU). A block must typically be erased in its entirety before data can be updated (re-written). In other words, flash-memory is typically used as a file store. File systems usually maintain data on the device in units of 512 bytes, commonly called sectors. The table in FIG. 1 illustrates the page/block/sector organization of several common flash-memory devices.
An external system typically transfers data to a flash-memory device in sets of contiguous sectors using a logical sector address and a sector count. A flash-media controller may be used to translate the logical sector address provided by the external system into a physical sector address on the flash-memory device. By convention, contiguous logical sectors that fall within the address range of a logical block are stored contiguously within the same physical block. The convention to keep sectors contiguous has several motivating factors. One is to avoid the cost of memory intensive look-up tables used to associate each logical sector with a physical sector. For example, a 128 MB flash-memory device will typically have 262,144 sectors. A per-sector lookup table would require at least one megabyte of storage. Another motivating factor is due to external systems typically transferring data in contiguous sectors using a first sector address and a sector count. Keeping the physical sectors contiguous generally erases a time penalty associated with a table lookup for each sector involved in the transfer.
Blocks may sometimes contain physically damaged electrical components. Damaged blocks are typically marked as invalid and are not used to store data. External systems are generally not designed to manage invalid blocks. Therefore, the flash-media controller must maintain a table of replacement blocks. This table may be used to translate logical addresses provided by external systems into physical addresses of valid blocks on the flash memory. Since some physical blocks may be invalid, it is not always possible to store logical blocks contiguously on the flash memory device.
External systems also frequently update (re-write) existing data. These updates take place within a few sectors of a block. A flash-media controller must typically establish a set of unused (or erased) pages to receive incoming data. Previously written data that falls outside the range of the current write operation must be preserved. Rewriting data on a flash memory device often entails re-arrangement of existing data using copy operations. As previously noted, this re-arrangement is necessary in order to maintain contiguous data and thereby minimize resources required to locate previously written data. The copy operations are generally time costly and interrupt the continuous flow of data from the external system to the flash memory, thereby reducing the overall write speed of the device.
There are currently a variety of methods used for re-arranging existing data on flash-memory devices. Sometimes, random access memory (RAM) or static random access memory (SRAM) resources are used for caching data prior to writing to the flash-memory device. At other times the data may be written to available read/write units and maintaining contiguous data may not even be attempted. One method involves assuming linear (contiguous) writes, and maintaining contiguous data by keeping a next-sector pointer. Relevant examples of current methods are presented in SMIL (SmartMedia™ Interface Library) Software Edition Version 1.00, Toshiba Corporation, published on Jul. 1, 2000, and in SMIL™ Standard 2000 Supplement Vol. 1, issued on Nov. 20, 2000 as part of the SSFDC Forum Technical Reference.
Caching solutions typically require significant temporary storage external to the flash-memory device, such as RAM or SRAM. Small inexpensive devices do not have storage sufficient for large re-write operations. Adding external storage resources typically adds significantly to the cost and complexity of the device. Resolving this issue may necessitate a mechanism to eliminate copy operations without requiring temporary storage external to the flash memory. Writing the data to available non-contiguous read/write units generally requires a larger and more complex lookup table. Larger flash memory devices may contain many thousands of read/write units, making the size of the lookup table prohibitive for a small inexpensive flash media controller.
Other corresponding issues related to the prior art will become apparent to one skilled in the art after comparing such prior art with the present invention as described herein.